Assignment 1 Solution

Question 1 Write a program to check whether a number is prime or not. Calculate its time complexity with proper explanation

Without Comments

import java.util.Scanner;

public class Q1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter a number : ");
        int number = scanner.nextInt();

        if(isPrime(number)){
            System.out.println(number+ " is a Prime Number.");
        }else{
            System.out.println(number+ " is not a Prime Number.");
        }

        scanner.close();
    }

    static boolean isPrime(int num) {
        if (num <= 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

With comments

import java.util.Scanner;

public class Q1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // create a scanner object to read input from the user
        System.out.print("Enter a number : ");
        int number = scanner.nextInt(); // read an integer input from the user

        // check if the input number is prime and print the result
        if(isPrime(number)){
            System.out.println(number+ " is a Prime Number.");
        }else{
            System.out.println(number+ " is not a Prime Number.");
        }

        scanner.close(); // close the scanner object to release resources
    }

    /**
     * Checks if a given number is prime or not
     * @param num the number to check
     * @return true if the number is prime, false otherwise
     */
    static boolean isPrime(int num) {
        if (num <= 1) { // 1 is not a prime number, so return false
            return false;
        }
        for (int i = 2; i <= Math.sqrt(num); i++) { // iterate from 2 to the square root of the number
            if (num % i == 0) { // if the number is divisible by any integer between 2 and its square root, then it's not prime
                return false;
            }
        }
        return true; // if the number is not divisible by any integer between 2 and its square root, then it's prime
    }
}

// The time complexity of this algorithm is O(sqrt(n)), where n is the input number. 
// This is because we iterate from 2 to the square root of n, which reduces the number of iterations required compared to iterating up to n itself. 
// Since the time complexity is proportional to the square root of the input, the algorithm is considered to be quite efficient for large inputs.

Credit:

Question 2 Write a program to find the binary equivalent of a decimal number. Calculate its time complexity

Without Comments

import java.util.Scanner;

public class Q2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter a number : ");
        int decimal = scanner.nextInt();

        System.out.print("The binary of " + decimal + " is: ");
        decToBinary(decimal);

        scanner.close();
    }

    static void decToBinary(int decimal) {
        int[] binary = new int[40];
        int index = 0;

        while (decimal > 0) {
            binary[index++] = decimal % 2;
            decimal /= 2;
        }

        for (int i = index - 1; i >= 0; i--) {
            System.out.print(binary[i]);
        }
    }
}

With comments

import java.util.Scanner;

public class Q2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // create a scanner object to read input from the user
        System.out.print("Enter a number : ");
        int decimal = scanner.nextInt(); // read an integer input from the user

        System.out.print("The binary of " + decimal + " is: ");
        decToBinary(decimal); // convert decimal to binary and print the result

        scanner.close(); // close the scanner object to release resources
    }

    /**
     * Converts a decimal number to binary representation and prints it
     * @param decimal the decimal number to convert
     */
    static void decToBinary(int decimal) {
        int[] binary = new int[40]; // array to store the binary digits
        int index = 0; // index to keep track of the current position in the binary array

        while (decimal > 0) {
            binary[index++] = decimal % 2; // calculate the remainder when divided by 2 and store it in the binary array
            decimal /= 2; // divide decimal by 2 to move to the next digit
        }

        for (int i = index - 1; i >= 0; i--) {
            System.out.print(binary[i]); // print the binary digits in reverse order
        }
    }
}

// The time complexity of this algorithm is O(log n), where n is the input decimal number. 
// This is because in each iteration, we divide the decimal number by 2, which effectively reduces the number of digits by half. 
// The number of iterations required to reduce the decimal number to 0 is proportional to log n. 
// Therefore, the algorithm is considered to be quite efficient for large inputs.

Credit:

Question 3 Write a program to find the reverse of a number and find its time complexity

Without Comments

import java.util.Scanner;

public class Q3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter a number : ");
        int number = scanner.nextInt();

        int reversedNumber = reverse(number);
        System.out.println("Reverse of " + number + " is " + reversedNumber);

        scanner.close();
    }

    static int reverse(int number) {
        int reversedNumber = 0;
        while (number != 0) {
            int digit = number % 10;
            reversedNumber = reversedNumber * 10 + digit;
            number /= 10;
        }
        return reversedNumber;
    }
}

With comments

import java.util.Scanner;

public class Q3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // create a scanner object to read input from the user
        System.out.print("Enter a number : ");
        int number = scanner.nextInt(); // read an integer input from the user

        int reversedNumber = reverse(number); // reverse the number
        System.out.println("Reverse of " + number + " is " + reversedNumber); // print the reversed number

        scanner.close(); // close the scanner object to release resources
    }

    /**
     * Reverses the digits of a given number
     * @param number the number to reverse
     * @return the reversed number
     */
    static int reverse(int number) {
        int reversedNumber = 0;
        while (number != 0) {
            int digit = number % 10; // extract the last digit of the number
            reversedNumber = reversedNumber * 10 + digit; // add the digit to the reversed number
            number /= 10; // remove the last digit from the number
        }
        return reversedNumber;
    }
}

// The time complexity of this algorithm is O(log n), where n is the input decimal number. 
// This is because in each iteration, we divide the number by 10, reducing its value by 10 times with each iteration. 
// The number of iterations required to reduce the number to 0 is proportional to log n. 
// Therefore, the algorithm is considered to be quite efficient for large inputs.

Credit:

Question 4 Write a program to search an element using binary search and calculate its time complexity

Without Comments

import java.util.Arrays;
import java.util.Scanner;

public class Q4 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter array size : ");
        int size = scanner.nextInt();

        int[] arr = new int[size];
        System.out.print("Enter array elements : ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }

        Arrays.sort(arr);

        System.out.print("Enter the element to be searched : ");
        int key = scanner.nextInt();

        int index = binarySearch(arr, size, key);

        if(index != -1){
            System.out.println("Element " + key + " found at index : " + index);
        } else {
            System.out.println("Element not found.");
        }

        scanner.close();
    }

    public static int binarySearch(int[] arr, int size, int key) {
        int low = 0;
        int high = size - 1;
        int mid;

        while (low <= high) {
            mid = (low + high) / 2;

            if (arr[mid] == key) {
                return mid;
            } else if (arr[mid] < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return -1;
    }
}

With comments

import java.util.Arrays;
import java.util.Scanner;

public class Q4 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // create a scanner object to read input from the user
        System.out.print("Enter array size : ");
        int size = scanner.nextInt(); // read the size of the array

        int[] arr = new int[size]; // create an array to store the elements
        System.out.print("Enter array elements : ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt(); // read each element of the array
        }

        Arrays.sort(arr); // sort the array in ascending order

        System.out.print("Enter the element to be searched : ");
        int key = scanner.nextInt(); // read the element to be searched

        int index = binarySearch(arr, size, key); // perform binary search

        if(index != -1){
            System.out.println("Element " + key + " found at index : " + index);
        } else {
            System.out.println("Element not found.");
        }

        scanner.close(); // close the scanner object to release resources
    }

    /**
     * Performs binary search on a sorted array to find a given element
     * @param arr the sorted array
     * @param size the size of the array
     * @param key the element to be searched
     * @return the index of the element if found, -1 otherwise
     */
    public static int binarySearch(int[] arr, int size, int key) {
        int low = 0;
        int high = size - 1;
        int mid;

        while (low <= high) {
            mid = (low + high) / 2; // calculate the middle index

            if (arr[mid] == key) { // if the middle element is equal to the key, return the index
                return mid;
            } else if (arr[mid] < key) { // if the middle element is less than the key, search in the right half
                low = mid + 1;
            } else { // if the middle element is greater than the key, search in the left half
                high = mid - 1;
            }
        }

        return -1; // element not found
    }
}

// The time complexity of this algorithm is O(log n), where n is the size of the input array. 
// This is because in each iteration of the binary search, we divide the search space in half, effectively reducing the size of the search space. 
// The number of iterations required to find the element is proportional to log n. 
// Therefore, the algorithm is considered to be quite efficient for large inputs.

Credit:

Question 5 Given an array, write a program to rotate its element K numbers of times. Explain its time complexity

Without Comments

import java.util.Scanner;

public class Q5 {
 public static void main(String[] args) {
  Scanner scanner = new Scanner(System.in);
  System.out.print("Enter array size : ");
  int size = scanner.nextInt();

  int[] arr = new int[size];
  System.out.print("Enter array elements : ");
  for (int i = 0; i < arr.length; i++) {
   arr[i] = scanner.nextInt();
  }

  System.out.print("Enter k : ");
  int k = scanner.nextInt();

  rotateArray(arr, k);

  scanner.close();
 }

 static void rotateArray(int[] arr, int k) {
  int temp;
  for (int j = 1; j <= k; j++) {
   temp = arr[0];

   for (int i = 0; i < arr.length - 1; i++) {
    arr[i] = arr[i + 1];
   }

   arr[arr.length - 1] = temp;
  }

  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + " ");
  }
 }
}

With comments

import java.util.*;

public class Q5 {
 public static void main(String[] args) {
  Scanner scanner = new Scanner(System.in); // create a scanner object to read input from the user
  System.out.print("Enter array size : ");
  int size = scanner.nextInt(); // read the size of the array

  int[] arr = new int[size]; // create an array to store the elements
  System.out.print("Enter array elements : ");
  for (int i = 0; i < arr.length; i++) {
   arr[i] = scanner.nextInt(); // read each element of the array
  }

  System.out.print("Enter k : ");
  int k = scanner.nextInt(); // read the value of k

  rotateArray(arr, k); // rotate the array by k positions

  scanner.close(); // close the scanner object to release resources
 }

 /**
  * Rotates an array by k positions to the right
  * @param arr the array to rotate
  * @param k the number of positions to rotate
  */
 static void rotateArray(int[] arr, int k) {
  int temp;
  for (int j = 1; j <= k; j++) {
   temp = arr[0]; // store the first element

   // Shift all elements to the left
   for (int i = 0; i < arr.length - 1; i++) {
    arr[i] = arr[i + 1];
   }

   arr[arr.length - 1] = temp; // place the stored element at the end
  }

  // Print the rotated array
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + " ");
  }
 }
}

Credit:

Question 6 Given an array of positive and negative integers, write a program to find a contiguous subarray whose sum of elements is maximum

Without Comments

import java.util.Scanner;

public class Q6 {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    System.out.print("Enter array size : ");
    int size = scanner.nextInt();

    int[] arr = new int[size];
    System.out.print("Enter array elements : ");
    for (int i = 0; i < arr.length; i++) {
      arr[i] = scanner.nextInt();
    }

    printArray(arr);

    maxSubarray(arr);

    scanner.close();
  }

  static void printArray(int[] arr) {
    System.out.print("The array is : ");
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

  static void maxSubarray(int[] nums) {
    int sum = 0;
    int max = nums[0];

    for (int i = 0; i < nums.length; i++) {
      sum += nums[i];
      if (sum > max)
        max = sum;
      if (sum < 0)
        sum = 0;
    }

    System.out.println("The maximum subarray sum is: " + max);
  }
}

With comments

import java.util.*;

public class Q6 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // create a scanner object to read input from the user
        System.out.print("Enter array size : ");
        int size = scanner.nextInt(); // read the size of the array

        int[] arr = new int[size]; // create an array to store the elements
        System.out.print("Enter array elements : ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt(); // read each element of the array
        }

        printArray(arr); // print the array

        maxSubarray(arr); // find the maximum subarray sum

        scanner.close(); // close the scanner object to release resources
    }

    /**
     * Prints the elements of an array
     * @param arr the array to print
     */
    static void printArray(int[] arr) {
        System.out.print("The array is : ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    /**
     * Finds the maximum subarray sum
     * @param nums the input array
     */
    static void maxSubarray(int[] nums) {
        int sum = 0;
        int max = nums[0];

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum > max)
                max = sum;
            if (sum < 0)
                sum = 0;
        }

        System.out.println("The maximum subarray sum is: " + max);
    }
}

Credit:

Question 7 Given an array, write a program to arrange its elements in waveform such that odd elements are lesser than its neighboring even elements

Without Comments

import java.util.Scanner;

public class Q7 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter array size : ");
        int size = scanner.nextInt();

        int[] arr = new int[size];
        System.out.print("Enter array elements : ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }

        printArray(arr);

        waveform(arr);

        scanner.close();
    }

    static void printArray(int[] arr) {
        System.out.print("The array is : ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void waveform(int[] arr) {
        for (int i = 0; i < arr.length - 1; i += 2) {
            if (i > 0 && arr[i - 1] > arr[i]) {
                swap(arr, i - 1, i);
            }
            if (arr[i] < arr[i + 1]) {
                swap(arr, i, i + 1);
            }
        }
        System.out.println("Waveform array is:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

With comments

import java.util.*;

public class Q7 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // create a scanner object to read input from the user
        System.out.print("Enter array size : ");
        int size = scanner.nextInt(); // read the size of the array

        int[] arr = new int[size]; // create an array to store the elements
        System.out.print("Enter array elements : ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt(); // read each element of the array
        }

        printArray(arr); // print the array

        waveform(arr); // convert the array to waveform

        scanner.close(); // close the scanner object to release resources
    }

    /**
     * Prints the elements of an array
     * @param arr the array to print
     */
    static void printArray(int[] arr) {
        System.out.print("The array is : ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    /**
     * Swaps two elements in an array
     * @param arr the array
     * @param a index of the first element
     * @param b index of the second element
     */
    static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    /**
     * Converts an array to its waveform representation
     * @param arr the input array
     */
    public static void waveform(int[] arr) {
        for (int i = 0; i < arr.length - 1; i += 2) {
            if (i > 0 && arr[i - 1] > arr[i]) {
                swap(arr, i - 1, i);
            }
            if (arr[i] < arr[i + 1]) {
                swap(arr, i, i + 1);
            }
        }
        System.out.println("Waveform array is:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Credit:

Question 8 Given an array of size N, containing elements from 0 to N-1. All values from 0 to N-1 are present in array and if they are not there than -1 is there to take place. Write a program to arrange values of the array so that value i is stored at arr[i]

Without Comments

import java.util.Scanner;

public class Q8 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter array size : ");
        int size = scanner.nextInt();

        int[] arr = new int[size];
        System.out.print("Enter array elements : ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }

        indexArray(arr);

        scanner.close();
    }

    static void indexArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (i != arr[i]) {
                for (int j = i; j < arr.length; j++) {
                    if (i == arr[j]) {
                        swap(arr, i, j);
                        break;
                    }
                }
                if (i != arr[i]) {
                    for (int j = i; j < arr.length; j++) {
                        if (arr[j] == -1) {
                            swap(arr, i, j);
                            break;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

With comments

import java.util.Scanner;

public class Q8 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter array size : ");
        int size = scanner.nextInt();

        int[] arr = new int[size];
        System.out.print("Enter array elements : ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }

        indexArray(arr);

        scanner.close();
    }

    /**
     * Rearranges the array such that each element is at the index equal to its value
     * @param arr the input array
     */
    static void indexArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (i != arr[i]) { // If the current element is not at the correct index
                for (int j = i; j < arr.length; j++) {
                    if (i == arr[j]) { // Find the element that should be at the current index
                        swap(arr, i, j); // Swap the elements
                        break;
                    }
                }
                if (i != arr[i]) { // If the element is still not at the correct index
                    for (int j = i; j < arr.length; j++) {
                        if (arr[j] == -1) { // Find an empty slot (-1) to place the element
                            swap(arr, i, j); // Swap the elements
                            break;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    /**
     * Swaps two elements in an array
     * @param arr the array
     * @param a index of the first element
     * @param b index of the second element
     */
    static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

Credit:

Question 9 Given an unsorted array, find the smallest positive number missing in the array

Without Comments

import java.util.*;

public class Q9 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter array size: ");
        int size = scanner.nextInt();

        int[] arr = new int[size];
        System.out.println("Enter array elements: ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }

        Arrays.sort(arr);

        findMissingNumber(arr);

        scanner.close();
    }

    static void findMissingNumber(int arr[]) {
        int missingNumber = 0;
        int containsOne = 0;

        for (int i = 0; i < arr.length - 1; i++) {
            if ((arr[0] > 0) && (arr[0] != 1)) {
                missingNumber = 1;
                break;
            } else if ((arr[i + 1] != arr[i] + 1) && (arr[i] + 1 > 0)) {
                missingNumber = arr[i] + 1;
                break;
            }
            if (arr[i] == 1)
                containsOne = 1;
        }

        if ((missingNumber != 0) && (containsOne != 1))
            System.out.println("Smallest positive missing number = 1");
        else if (missingNumber != 0)
            System.out.println("Smallest positive missing number = " + missingNumber);
        else
            System.out.println("No missing number");
    }
}

With comments

import java.util.*;

public class Q9 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter array size: ");
        int size = scanner.nextInt();

        int[] arr = new int[size];
        System.out.println("Enter array elements: ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }

        Arrays.sort(arr);

        findMissingNumber(arr);

        scanner.close();
    }

    /**
     * Finds the smallest positive missing number in the sorted array.
     *
     * @param arr the sorted array
     */
    static void findMissingNumber(int arr[]) {
        int missingNumber = 0;
        int containsOne = 0;

        for (int i = 0; i < arr.length - 1; i++) {
            if ((arr[0] > 0) && (arr[0] != 1)) {
                missingNumber = 1;
                break;
            } else if ((arr[i + 1] != arr[i] + 1) && (arr[i] + 1 > 0)) {
                missingNumber = arr[i] + 1;
                break;
            }
            if (arr[i] == 1)
                containsOne = 1;
        }

        if ((missingNumber != 0) && (containsOne != 1))
            System.out.println("Smallest positive missing number = 1"); // If the missingNumber is not found and the array doesn't contain 1, then the smallest positive missing number is 1.
        else if (missingNumber != 0)
            System.out.println("Smallest positive missing number = " + missingNumber); // If the missingNumber is found, print the smallest positive missing number.
        else
            System.out.println("No missing number"); // If the missingNumber is still 0, it means there are no missing positive numbers in the array.
    }
}

Credit:

Question 10 Given a sorted array, rearrange it in maximum-minimum form

Without Comments

import java.util.*;

public class Q10 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter array size: ");
        int size = scanner.nextInt();
        int arr[] = new int[size];
        System.out.print("Enter array elements: ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }
        Arrays.sort(arr);
        getMaxMin(arr);
        scanner.close();
    }

    static void getMaxMin(int arr[]) {
        int result[] = new int[arr.length];
        int start = 0, end = arr.length - 1;
        for (int i = 0; i < arr.length; i++) {
            if (i % 2 == 0) {
                result[i] = arr[end];
                end--;
            } else {
                result[i] = arr[start];
                start++;
            }
        }
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + " ");
        }
    }
}

With comments

import java.util.*;

public class Q10 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter array size: ");
        int size = scanner.nextInt();
        int arr[] = new int[size];
        System.out.print("Enter array elements: ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }
        Arrays.sort(arr);
        getMaxMin(arr);
        scanner.close();
    }

    // Rearranges the array in such a way that every alternate element
    // is either the maximum or minimum element from the sorted array
    static void getMaxMin(int arr[]) {
        int result[] = new int[arr.length];
        int start = 0, end = arr.length - 1;
        for (int i = 0; i < arr.length; i++) {
            if (i % 2 == 0) {
                result[i] = arr[end];  // Store the maximum element
                end--;
            } else {
                result[i] = arr[start];  // Store the minimum element
                start++;
            }
        }
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + " ");
        }
    }
}

Credit:

Question 11 Given an array you need to find the maximum sum of arr[i]*(i+1) for all elements such that you are allowed to rotate the array.

Without Comments

import java.util.*;

public class Q11 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter array size: ");
        int size = scanner.nextInt();
        int arr[] = new int[size];
        System.out.print("Enter array elements: ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }
        findMaxCircularSum(arr);
        scanner.close();
    }

    static void findMaxCircularSum(int arr[]) {
        int c, s = 0, sum;
        int circularSums[] = new int[arr.length];
        for (int j = 1; j <= arr.length; j++) {
            c = arr[0];
            sum = 0;
            for (int i = 0; i < arr.length - 1; i++) {
                arr[i] = arr[i + 1];
            }
            arr[arr.length - 1] = c;
            for (int i = 0; i < arr.length; i++) {
                sum = sum + (arr[i] * (i + 1));
            }
            circularSums[s] = sum;
            s++;
        }
        int max = circularSums[0];
        for (int i = 0; i < arr.length; i++) {
            if (max < circularSums[i]) {
                max = circularSums[i];
            }
        }
        System.out.println("Max = " + max);
    }
}

With comments

import java.util.*;

public class Q11 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter array size: ");
        int size = scanner.nextInt();
        int arr[] = new int[size];
        System.out.print("Enter array elements: ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }
        findMaxCircularSum(arr);
        scanner.close();
    }

    // Finds the maximum circular sum of the given array
    static void findMaxCircularSum(int arr[]) {
        int c, s = 0, sum;
        int circularSums[] = new int[arr.length];
        for (int j = 1; j <= arr.length; j++) {
            c = arr[0];  // Store the first element
            sum = 0;
            for (int i = 0; i < arr.length - 1; i++) {
                arr[i] = arr[i + 1];  // Shift elements to the left
            }
            arr[arr.length - 1] = c;  // Move the first element to the end
            for (int i = 0; i < arr.length; i++) {
                sum = sum + (arr[i] * (i + 1));  // Calculate the sum with weighted elements
            }
            circularSums[s] = sum;  // Store the circular sum
            s++;
        }
        int max = circularSums[0];
        for (int i = 0; i < arr.length; i++) {
            if (max < circularSums[i]) {
                max = circularSums[i];  // Find the maximum circular sum
            }
        }
        System.out.println("Max = " + max);
    }
}

Credit:

Question 12 Given an array arr[], find the maximum distance between indices i and j, such that arr[j] > arr[i]

Without Comments

import java.util.*;

public class Q12 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter array size: ");
        int size = scanner.nextInt();
        int arr[] = new int[size];
        System.out.print("Enter array elements: ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }
        int maxDifference = ArrayIndexMaxDiff(arr, size);
        System.out.println("The Maximum Difference is: " + maxDifference);
        scanner.close();
    }

    static int ArrayIndexMaxDiff(int[] arr, int size) {
        int maxDiff = -1;
        int j;
        for (int i = 0; i < size; i++) {
            j = size - 1;
            while (j > i) {
                if (arr[j] > arr[i]) {
                    maxDiff = Math.max(maxDiff, j - i);
                    break;
                }
                j -= 1;
            }
        }
        return maxDiff;
    }
}

With comments

import java.util.*;

public class Q12 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter array size: ");
        int size = scanner.nextInt();
        int arr[] = new int[size];
        System.out.print("Enter array elements: ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }
        int maxDifference = ArrayIndexMaxDiff(arr, size);
        System.out.println("The Maximum Difference is: " + maxDifference);
        scanner.close();
    }

    // Finds the maximum difference between the indices of two elements
    // such that the element at the later index is greater than the element at the earlier index
    static int ArrayIndexMaxDiff(int[] arr, int size) {
        int maxDiff = -1;
        int j;
        for (int i = 0; i < size; i++) {
            j = size - 1;
            while (j > i) {
                if (arr[j] > arr[i]) {
                    maxDiff = Math.max(maxDiff, j - i);  // Update maxDiff if a greater difference is found
                    break;
                }
                j -= 1;
            }
        }
        return maxDiff;
    }
}

Credit:

Question 13 Given two arrays in increasing order you need to find the maximum sum by choosing a few consecutive elements from one array and then a few elements from another array. The element switching can happen at transition points only when the element value is the same in both arrays

Without Comments

public class Q13 {
    public static void main(String[] args) {
        int arr1[] = {12, 13, 18, 20, 22, 26, 70};
        int arr2[] = {11, 15, 18, 19, 20, 26, 30, 31};
        findMaxPathSum(arr1, arr2);
    }

    static void findMaxPathSum(int arr1[], int arr2[]) {
        int i = 0, j = 0, result = 0, sum1 = 0, sum2 = 0;

        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] < arr2[j]) {
                sum1 += arr1[i];
                i++;
            } else if (arr1[i] > arr2[j]) {
                sum2 += arr2[j];
                j++;
            } else {
                result += Math.max(sum1, sum2);
                result += arr1[i];
                sum1 = 0;
                sum2 = 0;
                i++;
                j++;
            }
        }

        while (i < arr1.length) {
            sum1 += arr1[i];
            i++;
        }
        while (j < arr2.length) {
            sum2 += arr2[j];
            j++;
        }

        result += Math.max(sum1, sum2);
        System.out.println("Max Path sum = " + result);
    }
}

With comments

public class Q13 {
    public static void main(String[] args) {
        int arr1[] = {12, 13, 18, 20, 22, 26, 70};
        int arr2[] = {11, 15, 18, 19, 20, 26, 30, 31};
        findMaxPathSum(arr1, arr2);
    }

    // Finds the maximum path sum by traversing two sorted arrays
    static void findMaxPathSum(int arr1[], int arr2[]) {
        int i = 0, j = 0, result = 0, sum1 = 0, sum2 = 0;

        // Traverse both arrays simultaneously
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] < arr2[j]) {
                sum1 += arr1[i];
                i++;
            } else if (arr1[i] > arr2[j]) {
                sum2 += arr2[j];
                j++;
            } else {
                result += Math.max(sum1, sum2);  // Add the maximum sum so far to the result
                result += arr1[i];  // Add the common element to the result
                sum1 = 0;
                sum2 = 0;
                i++;
                j++;
            }
        }

        // If one array is exhausted, add the remaining elements of the other array to the respective sum
        while (i < arr1.length) {
            sum1 += arr1[i];
            i++;
        }
        while (j < arr2.length) {
            sum2 += arr2[j];
            j++;
        }

        result += Math.max(sum1, sum2);  // Add the remaining sum to the result
        System.out.println("Max Path sum = " + result);
    }
}

Credit:

Question 14 Write a recursive algorithm to solve the Tower of Hanoi problem

Without Comments

import java.util.Scanner;

public class Q14 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the number of discs: ");
        int num = scanner.nextInt();
        System.out.println("The sequence of moves is:");
        towerOfHanoi(num, 'A', 'C', 'B');
        scanner.close();
    }

    public static void towerOfHanoi(int numberOfDiscs, char source, char destination, char auxiliary) {
        if (numberOfDiscs < 1) {
            return;
        }
        towerOfHanoi(numberOfDiscs - 1, source, auxiliary, destination);
        System.out.println("Move disk " + numberOfDiscs + " from peg " + source + " to peg " + destination);
        towerOfHanoi(numberOfDiscs - 1, auxiliary, destination, source);
    }
}

With comments

import java.util.Scanner;

public class Q14 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the number of discs: ");
        int num = scanner.nextInt();
        System.out.println("The sequence of moves is:");
        towerOfHanoi(num, 'A', 'C', 'B');
        scanner.close();
    }

    // Solves the Tower of Hanoi puzzle for the given number of discs
    public static void towerOfHanoi(int numberOfDiscs, char source, char destination, char auxiliary) {
        if (numberOfDiscs < 1) {
            return;  // Base case: If the number of discs is less than 1, return
        }
        towerOfHanoi(numberOfDiscs - 1, source, auxiliary, destination);  // Move numberOfDiscs-1 discs from source to auxiliary peg
        System.out.println("Move disk " + numberOfDiscs + " from peg " + source + " to peg " + destination);
        towerOfHanoi(numberOfDiscs - 1, auxiliary, destination, source);  // Move numberOfDiscs-1 discs from auxiliary to destination peg
    }
}

Credit:

Question 15 Write a recursive function to find the GCD of two numbers. Write the recurrence of the function and solve it for a solution

Without Comments

import java.util.Scanner;

public class Q15 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter A: ");
        int a = scanner.nextInt();
        System.out.println("Enter B: ");
        int b = scanner.nextInt();
        System.out.print("The GCD of " + a + " and " + b + " is: " + calculateGCD(a, b));
        scanner.close();
    }

    public static int calculateGCD(int a, int b) {
        if (a < b) {
            return calculateGCD(b, a);
        }
        if (a % b == 0) {
            return b;
        }
        return calculateGCD(b, a % b);
    }
}

With comments

import java.util.Scanner;

public class Q15 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter A: ");
        int a = scanner.nextInt();
        System.out.println("Enter B: ");
        int b = scanner.nextInt();
        System.out.print("The GCD of " + a + " and " + b + " is: " + calculateGCD(a, b));
        scanner.close();
    }

    // Calculates the Greatest Common Divisor (GCD) of two numbers using the Euclidean algorithm
    public static int calculateGCD(int a, int b) {
        if (a < b) {
            return calculateGCD(b, a);  // Swap a and b if a is smaller than b
        }
        if (a % b == 0) {
            return b;  // Base case: If b divides a evenly, b is the GCD
        }
        return calculateGCD(b, a % b);  // Recursive case: Calculate GCD using the remainder (a % b)
    }
}

Credit:

Question 16 Write a program to find all permutations of an integer list recursively

Without Comments

import java.util.Scanner;

public class Q16 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter array size: ");
        int size = scanner.nextInt();
        int arr[] = new int[size];
        System.out.print("Enter array elements: ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }
        System.out.println("All the permutations of the array are:");
        permutation(arr, 0, size);
        scanner.close();
    }

    public static void permutation(int[] arr, int start, int length) {
        if (length == start) {
            printArray(arr, length);
            return;
        }
        for (int i = start; i < length; i++) {
            swap(arr, start, i);
            permutation(arr, start + 1, length);
            swap(arr, start, i);
        }
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void printArray(int[] arr, int length) {
        for (int i = 0; i < length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

With comments

import java.util.Scanner;

public class Q16 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter array size: ");
        int size = scanner.nextInt();
        int arr[] = new int[size];
        System.out.print("Enter array elements: ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }
        System.out.println("All the permutations of the array are:");
        permutation(arr, 0, size);
        scanner.close();
    }

    // Generates all permutations of the array
    public static void permutation(int[] arr, int start, int length) {
        if (length == start) {
            printArray(arr, length);
            return;
        }
        for (int i = start; i < length; i++) {
            swap(arr, start, i);
            permutation(arr, start + 1, length);
            swap(arr, start, i);
        }
    }

    // Swaps two elements in the array
    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // Prints the array
    static void printArray(int[] arr, int length) {
        for (int i = 0; i < length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Credit:

Question 17 Write a recursive function to search an element using binary search. Analyze its time complexity

Without Comments

import java.util.*;

public class Q17 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter array size: ");
        int size = scanner.nextInt();
        int arr[] = new int[size];
        System.out.print("Enter array elements: ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }
        Arrays.sort(arr);
        System.out.print("Enter the element to be searched: ");
        int key = scanner.nextInt();
        int index = binarySearchRecursive(arr, 0, size - 1, key);
        if (index != -1) {
            System.out.println("Element " + key + " found at index: " + index);
        } else {
            System.out.println("Element not found.");
        }
        scanner.close();
    }

    public static int binarySearchRecursive(int[] arr, int low, int high, int key) {
        if (low > high)
            return -1;
        int mid = (low + high) / 2;
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            return binarySearchRecursive(arr, mid + 1, high, key);
        } else {
            return binarySearchRecursive(arr, low, mid - 1, key);
        }
    }
}

With comments

import java.util.*;

public class Q17 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter array size: ");
        int size = scanner.nextInt();
        int arr[] = new int[size];
        System.out.print("Enter array elements: ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }
        Arrays.sort(arr);
        System.out.print("Enter the element to be searched: ");
        int key = scanner.nextInt();
        int index = binarySearchRecursive(arr, 0, size - 1, key);
        if (index != -1) {
            System.out.println("Element " + key + " found at index: " + index);
        } else {
            System.out.println("Element not found.");
        }
        scanner.close();
    }

    // Recursive binary search implementation
    public static int binarySearchRecursive(int[] arr, int low, int high, int key) {
        if (low > high)
            return -1;
        int mid = (low + high) / 2;
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            return binarySearchRecursive(arr, mid + 1, high, key);
        } else {
            return binarySearchRecursive(arr, low, mid - 1, key);
        }
    }
}

Credit: